package arithmetic2;

import org.quartz.impl.jdbcjobstore.FiredTriggerRecord;

/**
 * Created by AJie on 2019/7/24
 * Function :
 * 最长回文子串
 *
 * 题目描述
 * 提交记录
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 示例 1：
 *
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 *
 * 输入: "cbbd"
 * 输出: "bb"
 */
public class T_005_LongestPalindromicSubstring {
    public static void main(String[] args) {

        //暴力法
        //将选出所有子字符串可能的开始和结束位置，并检验它是不是回文。
        //start 0-n  end i-n
        //https://leetcode-cn.com/problems/two-sum/solution/zui-chang-hui-wen-zi-chuan-by-leetcode/
        //时间复杂度：O(n^3)
        //空间复杂度：O(1)O(1)。

        //动态规划
        //递推，最小最优解  ++
//        String babad = longestPalindrome2("babad");
        String babad = longestPalindromeDY("babad");
        System.out.println(babad);

    }

//    * 1、递推！！！=（递归 + 记忆化）
//            * 2、状态的定义 ： opt[n],dp[n],fib[n] * opt 数组 * dp 方程
//* 3、状态转移方程： opt[n] = best_of (opt[n-1],opt[n-2],...)
//* 4、最优子结构 （目的：可以有小推大，递推

        public static String longestPalindrome2(String s) {
            int len = s.length();
            if (len <= 1) {
                return s;
            }
            int longestPalindrome = 1;
            String longestPalindromeStr = s.substring(0, 1);
            boolean[][] dp = new boolean[len][len];
            // abcdedcba
            //   l   r
            // 如果 dp[l, r] = true 那么 dp[l + 1, r - 1] 也一定为 true
            // 关键在这里：[l + 1, r - 1] 一定至少有 2 个元素才有判断的必要
            // 因为如果 [l + 1, r - 1] 只有一个元素，不用判断，一定是回文串
            // 如果 [l + 1, r - 1] 表示的区间为空，不用判断，也一定是回文串
            // [l + 1, r - 1] 一定至少有 2 个元素 等价于 l + 1 < r - 1，即 r - l >  2

            // 写代码的时候这样写：如果 [l + 1, r - 1]  的元素小于等于 1 个，即 r - l <=  2 ，就不用做判断了

            // 因为只有 1 个字符的情况在最开始做了判断
            // 左边界一定要比右边界小，因此右边界从 1 开始
            for (int r = 1; r < len; r++) {
                for (int l = 0; l < r; l++) {
                    System.out.println("left "+l +" right"+r);
                    // 区间应该慢慢放大
                    // 状态转移方程：如果头尾字符相等并且中间也是回文
                    // 在头尾字符相等的前提下，如果收缩以后不构成区间（最多只有 1 个元素），直接返回 True 即可
                    // 否则要继续看收缩以后的区间的回文性
                    // 重点理解 or 的短路性质在这里的作用
                    if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                        dp[l][r] = true;
                        if (r - l + 1 > longestPalindrome) {
                            longestPalindrome = r - l + 1;
                            longestPalindromeStr = s.substring(l, r + 1);
                        }
                    }
                }
            }
            return longestPalindromeStr;
        }

    public static String longestPalindromeDY(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        boolean[][] dp = new boolean[len][len];

        // 初始化
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        int maxLen = 1;
        int start = 0;

        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {

                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i < 3) {//长度小于4 (j-i +1) <4 即： 1个肯定回文 ，2个串 ，3个串=2+1
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                } else {
                    dp[i][j] = false;
                }

                // 只要 dp[i][j] == true 成立，就表示子串 s[i, j] 是回文，此时记录回文长度和起始位置
                if (dp[i][j]) {
                    int curLen = j - i + 1;
                    if (curLen > maxLen) {
                        maxLen = curLen;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start, start + maxLen);
    }


    //中心扩散法 todo 没有搞懂

    /**
     *
     *  链接：https://leetcode-cn.com/problems/two-sum/solution/zui-chang-hui-wen-zi-chuan-by-leetcode/
     * 中心扩散法的想法很简单：遍历每一个索引，以这个索引为中心，
     * 利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。
     * 要注意一个细节：回文串的长度可能是奇数，也可能是偶数。
     *
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/problems/two-sum/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }

}
